package heap;

/**
 * 使用小堆来维护
 * 对象的正确性检查
 * size >= 0
 * array != null
 * array + size 满足小堆的性质
 * 堆的定义：要求每个位置都比它的两个孩子小(如果孩子存在的话)
 */
public class MyPriorityQueuePrimitiveType {
    //元素使用 long 类型
    //暂时不考虑扩容的情况
    private final long[] array = new long[1000];
    private int size;       //元素个数
    private static void assertTrue(boolean condition,String message){
        if(!condition){
            throw new RuntimeException(message);
        }
    }
    private static void assertSmallHeap(long[] array,int size){
        for(int i = 0;i < size;i++){
            if(2 * i + 1 < size){
                assertTrue(array[i] <= array[2 * i + 1],"我的值必须比我的左孩子的值小");
            }
            if(2 * i + 2 < size){
                assertTrue(array[i] <= array[2 * i + 2],"我的值必须比我的右孩子的值小");
            }
        }
    }
    public void checkIsTrue(){
        assertTrue(size >= 0,"size 必须大于等于 0");
        assertTrue(size <= 1000,"size 必须小于等于容量1000");
        assertTrue(array != null,"array 必须右数组");
        assertSmallHeap(array,size);
    }
    public MyPriorityQueuePrimitiveType(){
        //空的优先级队列
        size = 0;
        checkIsTrue();
    }

    //小堆的非递归向下调整
    public void adjustDownSmallHeap1(int index){
        while (2 * index + 1 < size){       //判断是不是叶子结点，即有没有左孩子
            //找到最小的孩子
            int minIdx = 2 * index + 1;     //先将左孩子定为最小孩子
            //判断左孩子和右孩子哪一个更小
            if(minIdx + 1 < size && array[minIdx + 1] < array[minIdx]){
                minIdx++;
            }
            //判断 “我” 和最小结点的值的大小关系
            if (array[index] <= array[minIdx]){
                return;
            }
            //“我” 这个结点不小于当前最小结点的值时进行交换
            swap(array,index,minIdx);
            //以最小孩子的位置再一次进行循环
            index = minIdx;
        }
    }
    public void swap(long[] array,int i,int j){
        long t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    //查看优先级队列中的最小值
    //因为是小堆，所以最小值就是第一个元素
    public long peek(){
        if(size <= 0){
            throw new RuntimeException("空的优先级队列");
        }
        return array[0];
    }

    //把 e 添加到堆(优先级队列)中
    //同时维护好堆的性质
    //最坏的情况：从叶子到根都经过一次
    //O(log(n))
    public void offer(long e){
        array[size] = e;
        size++;
        int index = size - 1;
        while (index != 0){
            //求双亲的下标
            int pIdx = (index - 1) / 2;
            //比较要调整的位置和双亲的大小
            if(array[pIdx] <= array[index]){
                break;
            }
            swap(array,index,pIdx);
            index = pIdx;
        }
        //在添加结束后检查一下调整后的优先级队列是否正确
        checkIsTrue();
    }

    //删除堆顶元素
    //同时维护好最小堆的性质
    //O(log(n))
    public long poll(){
        if(size < 0){
            throw new RuntimeException("空的优先级队列");
        }
        long e = array[0];
        array[0] = array[size - 1];
        array[size - 1] = 0;
        size--;
        adjustDownSmallHeap1(0);
        checkIsTrue();
        return e;
    }

    public static void main(String[] args) {
        MyPriorityQueuePrimitiveType q = new MyPriorityQueuePrimitiveType();

        q.offer(3);
        q.offer(9);
        q.offer(7);
        q.offer(2);
        q.offer(6);
        q.offer(8);
        q.offer(5);
        q.offer(4);
        q.offer(3);

        System.out.println(q.poll());       //2
        q.offer(1);
        System.out.println(q.poll());       //1
        q.offer(1);
        q.offer(0);
        System.out.println(q.poll());       //0
        System.out.println(q.poll());       //1
    }
}
